package org.example.dp.split;

import java.util.Arrays;

/**
 * @Description: TODO
 * @Author wyatt
 * @Data 2024/05/13 19:36
 */

//一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
//
//
//'A' -> "1"
//'B' -> "2"
//...
//'Z' -> "26"
//
// 要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：
//
//
// "AAJF" ，将消息分组为 (1 1 10 6)
// "KJF" ，将消息分组为 (11 10 6)
//
//
// 注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。
//
// 给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
//
// 题目数据保证答案肯定是一个 32 位 的整数。
//
//
//
// 示例 1：
//
//
//输入：s = "12"
//输出：2
//解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
//
//
// 示例 2：
//
//
//输入：s = "226"
//输出：3
//解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
//
//
// 示例 3：
//
//
//输入：s = "06"
//输出：0
//解释："06" 无法映射到 "F" ，因为存在前导零（"6" 和 "06" 并不等价）。
//
//
//
//
// 提示：
//
//
// 1 <= s.length <= 100
// s 只包含数字，并且可能包含前导零。
//
//
// Related Topics 字符串 动态规划 👍 1520 👎 0

public class Solution91 {

    public static void main(String[] args) {
        Solution91 solution = new Solution91();
        System.out.println(solution.numDecodings("2611055971756562"));
    }

    // 假设 没有 0 数字小于 3
    // 1 1
    // 12 2
    // 121 3
    // 1212 5
    // 12121 8
    // dp[n] = dp[n-1] + dp[n-2]
    // 如果无法单独或者无法跟前一个数字组合， dp[n] = dp[n-1]
    public int numDecodings(String s) {
        int n = s.length();
        int[] arr = new int[n];
        int index=0;
        for(Character c : s.toCharArray()){
            int num = Character.getNumericValue(c);
            if(index == 0 && num == 0){
                return 0;
            }else if(num == 0){
                if(arr[index-1] <=0 || arr[index-1] > 2){
                    return 0;
                }
                arr[index-1] = -1;
                arr[index] = -1;
            } else {
                arr[index] = num;
            }

            index++;
        }

        if(arr[0]  == 0 ){
            return 0;
        }

        if(n < 2){
            return 1;
        }

        int[] dp = new int[n];
        dp[0] = 1;
        if(arr[0] > 2 || arr[1] <= 0 || arr[0]*10 + arr[1] > 26){
            dp[1] = 1;
        }else {
            dp[1] = 2;
        }

        for(int i=2;i<arr.length;i++){
            if(arr[i] <= 0 || arr[i-1] > 2 || (arr[i-1]*10 + arr[i] > 26) || arr[i-1] <= 0){
                dp[i] = dp[i-1];
            }else {
                dp[i] = dp[i-1] + dp[i-2];
            }
        }

        return dp[n-1];
    }

}
